package linkedlist;

import java.util.List;

/**
 * K 个一组翻转链表
 */
public class ReverseNodesInKGroup {

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5};
        ListNode head = ListNode.generateLinkedList(nums);
        Solution2 solution = new Solution2();
        ListNode newHead = solution.reverseKGroup(head, 2);
        List<Integer> traverse = ListNode.traverseLinkedList(newHead);
        for (Integer num : traverse) {
            System.out.println(num + " ");
        }
    }

    static class Solution3 {
        public ListNode reverseKGroup(ListNode head, int k) {

            if (head == null || k == 1) {
                return head;
            }

            ListNode cur = head, newHead = null, lastNode = null;
            while (cur != null) {
                ListNode start = cur, end = null;
                int cnt = 1;

                while (cnt < k && cur != null) {
                    cur = cur.next;
                    cnt++;
                }
                if (cnt == k) {
                    end = cur;
                    if (cur != null) {
                        cur = cur.next;
                    }
                }
                // nodes[0] 反转以后的头 nodes[1] 反转后的end
                ListNode[] nodes = reverseLinkedList(start, end);
                // 第一次翻转才回去初始化 反转后的node
                if (newHead == null) {
                    newHead = nodes[0];
                }
                if (lastNode != null) {
                    lastNode.next = nodes[0];
                    lastNode = nodes[1];
                } else {
                    lastNode = nodes[1];
                }
            }
            return newHead;
        }

        public ListNode[] reverseLinkedList(ListNode start, ListNode end) {
            ListNode[] nodes = new ListNode[2];
            // 说明链表数不够 k 无需翻转
            if (end == null) {
                nodes[0] = start;
                nodes[1] = end;
                return nodes;
            }
            ListNode cur = start, last = null;
            while (cur != end) {
                ListNode next = cur.next;
                cur.next = last;
                last = cur;
                cur = next;
            }
            cur.next = last;
            nodes[0] = end;
            nodes[1] = start;
            return nodes;
        }
    }

    /**
     * 使用迭代
     */
    static class Solution2 {
        public ListNode reverseKGroup(ListNode head, int k) {
            if (head == null || k == 1 || getKthNodeFromCur(head, k) == null) {
                return head;
            }
            ListNode prev = new ListNode(-1), cur = head;
            head = getKthNodeFromCur(head, k);
            while (getKthNodeFromCur(cur, k) != null) {
                ListNode kthNodeFromCur = getKthNodeFromCur(cur, k);
                //存储kthNodeFromCur的下一个节点
                ListNode next = kthNodeFromCur.next;
                //翻转以后kthNodeFromCur变为这个区间内链表的头节点，reverseKNode返回这个区间的最后一个节点
                ListNode last = reverseKNode(cur, kthNodeFromCur);
                prev.next = kthNodeFromCur;
                prev = last;
                cur = next;
            }
            prev.next = cur;
            return head;
        }

        public ListNode getKthNodeFromCur(ListNode head, int k) {
            int count = 1;
            ListNode cur = head;
            while (cur != null) {
                cur = cur.next;
                count++;
                if (count == k) {
                    return cur;
                }
            }
            return null;
        }

        public ListNode reverseKNode(ListNode head, ListNode end) {
            if (head == end) {
                return head;
            }
            ListNode prev = reverseKNode(head.next, end);
            prev.next = head;
            return head;
        }
    }

    /**
     * 使用递归
     */
    static class Solution1 {

        /**
         * k个一组翻转链表，如果k==1,则不发生翻转
         * <p>
         * 给定链表：1->2->3->4->5
         * 当 k = 2 时，应当返回: 2->1->4->3->5
         * 当 k = 3 时，应当返回: 3->2->1->4->5
         *
         * @param head
         * @param k
         * @return
         */
        public ListNode reverseKGroup(ListNode head, int k) {
            //k = 1，时，不发生翻转,head == null说明是走到了末尾或者是head为null
            if (head == null || k == 1) {
                return head;
            }
            ListNode next;
            ListNode kthNodeFromHead = getKthNodeFromHead(head, k);
            if (kthNodeFromHead != null) {
                next = reverseKGroup(kthNodeFromHead.next, k);
            } else {
                return head;
            }

            //对当前的k个元素进行翻转，翻转以后，最后一个元素变为第一个元素，第一个元素变为最后一个元素
            ListNode last = reverseKNode(head, kthNodeFromHead);
            last.next = next;
            return kthNodeFromHead;
        }

        /**
         * 获得从当前的head节点开始的第K个节点,比如head -> 1 -> 2 -> 3 -> 4获得k = 3的节点,
         * 即返回值为3的这个节点
         *
         * @param head
         * @param k
         * @return 如果能得到第K个节点，则返回该节点，否则返回Null
         */
        public ListNode getKthNodeFromHead(ListNode head, int k) {
            int count = 1;
            ListNode cur = head;
            while (cur != null) {
                cur = cur.next;
                count++;
                if (count == k) {
                    return cur;
                }
            }
            return null;
        }

        /**
         * 使用递归翻转指定区间内的节点
         * 返回翻转以后的链表的最后一个节点，比如翻转[head -> 1 -> 2 -> 3 ]
         * 翻转以后变为[3 -> 2 -> 1],返回1这个节点
         *
         * @param head
         * @param end
         * @return
         */
        public ListNode reverseKNode(ListNode head, ListNode end) {
            if (head == end) {
                return head;
            }
            ListNode prev = reverseKNode(head.next, end);
            prev.next = head;
            return head;
        }
    }

}
